import java.util.ArrayList;
import java.util.List;

public class 全排列 {
    
    public static void main(String[] args) {
        
        int[] nums = new int[]{1,2,3};


        //创建一个二维列表，赋全排列的值
        List<List<Integer>> permutations = new ArrayList<>();
        //表示当前排列
        List<Integer> current = new ArrayList<>();
        
        //用于标记某数字是否使用过
        //boolean[] used = new boolean[nums.length];
        backtrack(nums, current, permutations);
        
        //输出打印结果
        for (List<Integer> permutation : permutations) {
            for (int num : permutation) {
                System.out.print(num+"  ");
            }
            System.out.println();
        }

    }

    //回溯算法
    private static void backtrack(int[] nums, List<Integer> current,
                                  List<List<Integer>> permutations) {
        //当前排列排满后 添加到总排列表中并该次递归
    	if (current.size() == nums.length) {
            permutations.add(new ArrayList<>(current));
            return;
        }
 
    	
        for (int i = 0; i < nums.length; i++) {
        	//当数字未被使用
            // if (!used[i]) {
            //     used[i] = true;	//标记为已使用
            //     current.add(nums[i]); //添加数字
                
            //     //继续搜索数字并添加。最后会添加
            //     backtrack(nums, current, permutations);  
                
 
            //     //回溯
            //     current.remove(current.size() - 1);  //移除这个数字
            //     //used[i] = false;  // 标记为未使用
            // }

            if(current.contains(nums[i])) continue;
            current.add(nums[i]); //添加数字
                
            //继续搜索数字并添加。最后会添加
            backtrack(nums, current, permutations);  
            //回溯
            current.remove(current.size() - 1);  //移除这个数字
        } 
    }
}
